for the global pair-wise homology alignment. Using these

ms, every residue of two sequences is used in an alignment. The

mology alignment only focuses on the segments which are the

ilar to each other. The Smith-Waterman alignment algorithm is

pical algorithm [Smith and Waterman, 1981].

he alignment metric and moving directions

rithm uses a uniform positive score for an exact match, which is

gative score for a mismatch, which is −0.3 and a length-dependent

alty, which is defined below with L denoting the number of

us gaps or the length of a gap segment inserted into a sequence,

ܩ௅ൌെ1 െܮ3

⁄

(7.12)

moving directions used are from the top-left corner cell to the

ght corner cell in a dynamic programming table as shown in

3, where ݏ௜௝ is the alignment score between the i^th residue of

x and the j^th residue of sequence y, ܯ௜௝ is the score of the

optimised alignment till the cell (i, j) in the table. For the cell (i,

can be three moving directions for an alignment. If no gap is

a move is from the cell (iെ1, jെ1) to the cell (i, j) meaning both

idue of sequence x and the j^th residue of sequence y are used for

remental alignment. This is called the diagonal move in the table.

Fig. 7.3. The moving directions for the Smith-Waterman update rule.

i^th residue of sequence x is aligned with a gap, no residue from

y will be picked up. This means that the j^th residue of sequence y